package com.xxwy.sort.nlogn;

import com.xxwy.sort.Sort;

/**
 * @author xxwy
 * 自底向上的归并排序，
 */
public class MergeSortBU implements Sort {
    @Override
    public void sort(int[] array, int n) {

        for (int sz = 1; sz <= n; sz += sz) {
            //下面的参数为什么是两个sz，是因为i到下一次的开始查了两个sz
            for (int i = 0; i < n; i += sz + sz) {
                //对array[i...i+sz-1]和arr[i+sz...i+2*sz-1]
                if (i + sz < n && array[i + sz - 1] > array[i + sz]) {
                    merge(array, i, i + sz - 1, min(i + sz + sz - 1, n - 1));
                }
            }
        }
    }

    private int min(int r1, int r2) {
        return r1 < r2 ? r1 : r2;
    }

    private void merge(int[] arr, int l, int mid, int r) {
        int[] aux = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
            aux[i - l] = arr[i];
        }
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l] < aux[j - l]) {
                arr[k] = aux[i - l];
                i++;
            } else {
                arr[k] = aux[j - l];
                j++;
            }

        }
    }
}
